Transactions on Combinatorics
Volume:11 Issue: 1, Mar 2022

In this article‎, ‎we discuss the vertex decomposability of three well-studied simplicial complexes associated to forests‎. ‎In particular‎, ‎we show that the bounded degree complex of a forest and the complex of directed trees of a multidiforest is vertex decomposable‎. ‎We then prove that the non-cover complex of a forest is either contractible or homotopy equivalent to a sphere‎. ‎Finally we provide a complete characterization of forests whose non-cover complexes are vertex decomposable‎.

The deterministic permutation flow shop scheduling problem with makespan criterion is not solvable in polynomial time‎. ‎Therefore‎, ‎researchers have thought about heuristic algorithms‎. ‎There are many heuristic algorithms for solving it that is a very important combinatorial optimization problem‎. ‎In this paper‎, ‎a new algorithm is proposed for solving the mentioned problem‎. ‎The presented algorithm chooses the weighted path that starts from the up-left corner and reaches the down-right in the matrix of jobs processing times and calculates the biggest sum of the times in the footprints of this path‎. ‎The row with the biggest sum permutes among all the rows of the matrix for locating the minimum of makespan‎. ‎This method was run on Taillard’s standard benchmark and the solutions were compared with the optimum or the best ones as well as 14 famous heuristics‎. ‎The validity and effectiveness of the algorithm are shown with tables and statistical evaluation‎.

In this paper‎, ‎we delve into studying some relations between the structure of the cycles and spanning trees of a graph through the lens of its cycle and spanning tree hypergraphs which are hypergraphs with the edge set of the graph as their vertices and the edge sets of the cycles and spanning trees as their hyperedges respectively‎. ‎In particular‎, ‎we investigate relations between these hypergraphs from the perspective of the VC-dimension and some important separating and covering features of hypergraph theory and amongst the results‎, ‎for example show that the VC-dimension of the cycle hypergraph is less than or equal to the VC-dimension of the spanning tree hypergraph and their gap can be arbitrary large. Note that VC-dimension is an important measure of complexity and a fundamental notion in numerous fields such as extremal combinatorics‎, ‎graph theory‎, ‎statistics and the theory of machine learning‎. ‎Also we compare the separating and covering features of the mentioned hypergraphs and for instance show that the separating number of the cycle hypergraph is less than or equal to that of the spanning tree hypergraph‎. ‎These hypergraphs help us to make several connections between cycles and spanning trees of graphs and compare their complexities‎.

The energy of a graph is the sum of the absolute values of the eigenvalues of a graph‎. ‎Two graphs are said to be equienergetic if they have same energy‎. ‎A graph is said to be complementary equienergetic if it is equienergetic with its complement‎. ‎Recently several complementary equienergetic graphs have been identified‎. ‎In this paper‎, ‎we characterize the cycles‎, ‎paths‎, ‎complete bipartite regular graphs and iterated line graphs of regular graphs‎, ‎which are complementary equienergetic‎.
.

A claw is a star with three edges. The Kneser graph KGn,2 is the graph whose vertices are the 2-subsets of an n-set, in which two vertices are adjacent if and only if their intersection is empty. In this paper, we prove that KGn,2 is claw-decomposable, for all n ≥ 6.